package pl.pw.eiti.mkoi.squfof;

import java.util.HashSet;
import android.util.Log;

public class SqufofFactorisation extends Factorisation {

	@SuppressWarnings("unused")
    private static final String LOG_TAG = SqufofFactorisation.class.getSimpleName();

	@Override
	public Integer getFactor(Integer number) {

		int N = number.intValue();
		
		if (N == 0) return 1;
		if (N == 1) return 1;
		if (N < 0) return getFactor(new Integer(-1*N));

        
		//step 1
        HashSet<Double> list = new HashSet<Double>();
        double P = 0,P_next,Q_prev = 1,Q,Q_next,q,sqrt;
        final double n = 2*Math.sqrt(2*Math.sqrt(N));
        int i = 1;
        
        q = Math.floor(Math.sqrt(N));
        P_next = q; Q =  N - P_next*P_next;
        sqrt = Math.sqrt(Q);
        if(Q==0){
            return new Integer((int)P_next);
        }
        if(Q < n){
            list.add(Q);
        }

        P = P_next;

        while(!(Math.floor(sqrt)==sqrt && i%2==0 && !(sqrt%2==0?list.contains(sqrt/2):list.contains(sqrt)))){

            q = Math.floor((Math.sqrt(N)+P)/Q);
            P_next = q*Q - P;
            Q_next = Q_prev + (P - P_next)*q;
            
            if(Q < n){
                list.add(Q);
            }
            
            Q_prev = Q;
            Q = Q_next;
            P = P_next;

            sqrt = Math.sqrt(Q);
            if(sqrt == 1.0D){
                return 1;
            }
            ++i;

        }

        //step 2
        P = -P;
        Q_prev = sqrt;
        P_next = q*Q_prev - P; 
        Q = (N - P_next*P_next)/Q_prev;
        P = P_next;


        while(true){

            q = Math.floor((Math.sqrt(N)+P)/Q);
            P_next = q*Q - P;

            Q_next = Q_prev + (P - P_next)*q;

            if(P==P_next) break;

            Q_prev = Q;
            Q = Q_next;
            P = P_next;
        }

		return new Integer((int)(Q%2==0?Q/2:Q));
	}
	
}
